iT邦幫忙

2021 iThome 鐵人賽

DAY 22
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 22

【Day22】[演算法]-選擇排序法Selection Sort

  • 分享至 

  • xImage
  •  

選擇排序法(Selection Sort),原理是反覆從未排序數列中找出最小值,將它與左邊的數做交換。可以有兩種方式排序,一為由大到小排序時,將最小值放到末端;若由小到大排序時,則將最小值放到前端。例如:未排序的數列中找到最小值的資料,和第1筆資料交換位置,再從剩下未排序的資料列中找到最小值的資料,和第2筆資料交換位置,以此類推。

下面利用40 30 60 50 20由小到大排序。
https://ithelp.ithome.com.tw/upload/images/20211003/20121027Z3FUzMHujx.jpg


n=5
第1回合在4個數中找最小值,找4次,n-1次
第2回合在3個數中找最小值,找3次,n-2次
第3回合在2個數中找最小值,找2次,n-3次
第4回合在1個數中找最小值,找1次,n-4次
總共找了4回合,n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均時間複雜度為: O(n²)


JavaScript

let data = [8,6,1,10,5,3,9,2,7,5]

function SelectionSort(array) { 
  let n = array.length;
  for(let i = 0; i < n; i++) {
    let min = i;
    for(let j = i+1; j < n; j++){
      if(array[j] < array[min]) {
        //記憶最小值的位置
        min=j; 
      }
    }
    if (min != i) {
      [array[i], array[min]] = [array[min], array[i]]; 
    }
  }
  return array;
}
console.log(SelectionSort(data))//[1, 2, 3, 5, 5, 6, 7, 8, 9, 10]

Python

#Selection Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def SelectionSort(data):
    n = len(data)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if data[j] < data[min_idx]:
                min_idx = j
        if min_idx != i:
            data[i], data[min_idx] = data[min_idx], data[i]
    return data        

print(SelectionSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

上一篇
【Day21】[演算法]-排序Sort & 氣泡排序法Bubble Sort
下一篇
【Day23】[演算法]-插入排序法Insertion Sort
系列文
資料結構與演算法,使用JavaScript與Python35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言